Implement Stack using Queues

Implement the following operations of a stack using queues.

  • push(x) — Push element x onto stack.
  • pop() — Removes the element on top of the stack.
  • top() — Get the top element.
  • empty() — Return whether the stack is empty.

Notes:

  • You must use only standard operations of a queue — which means only push to back, peek/pop from front, size, and is empty operations are valid.
  • Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
  • You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Solution:

  1. class MyStack {
  2.   Queue<Integer> queue = new LinkedList<Integer>();
  4.   // Push element x onto stack.
  5.   public void push(int x) {
  6.     queue.add(x);
  7.     int k = queue.size();
  8.     while (k-- > 1) {
  9.       queue.add(queue.poll());
  10.     }
  11.   }
  13.   // Removes the element on top of the stack.
  14.   public void pop() {
  15.     queue.poll();
  16.   }
  18.   // Get the top element.
  19.   public int top() {
  20.     return queue.peek();
  21.   }
  23.   // Return whether the stack is empty.
  24.   public boolean empty() {
  25.     return queue.isEmpty();
  26.   }
  27. }